We explore to what extent path-integral quantum Monte Carlo methods canefficiently simulate the tunneling behavior of quantum adiabatic optimizationalgorithms. Specifically we look at symmetric cost functions defined over nbits with a single potential barrier that a successful optimization algorithmwill have to tunnel through. The height and width of this barrier depend on n,and by tuning these dependencies, we can make the optimization algorithmsucceed or fail in polynomial time. In this article we compare the strength ofquantum adiabatic tunneling with that of path-integral quantum Monte Carlomethods. We find numerical evidence that quantum Monte Carlo algorithms willsucceed in the same regimes where quantum adiabatic optimization succeeds.
展开▼
